#include <conio.h>
#include <iostream>
using namespace std;

#define SIZE 100000000

#define NORTH   8
#define SOUTH   -3
#define WEST    -6
#define EAST    5
#define MAXDEPTH    15

int leastSteps = 1000000;
static string directions[4] = { "north", "south", "west", "east" };
static int movement[4] = { NORTH, SOUTH, WEST, EAST };
#define N   0
#define S   1
#define W   2
#define E   3


template <class Qtype> class MyQueue {
    Qtype queue[SIZE];
    int first, last, size;

    public:

    MyQueue(){
        first = 0; last = 0; size = 0;
    }

    void enQueue(Qtype newElem){
        if(last+1 == first || (last+1 == SIZE && first == 0)){
            cout << "Error, queue is full!" << endl;
            return;}

        last++; size++;
        if(last==SIZE)
            last = 0;
        queue[last] = newElem;
    }

    Qtype deQueue(){
        if(first == last){
            cout << "You tried getting object from empty queue!" << endl;
            //return NULL; <-- replace with throw statement plx
            }

        first++; size--;
        if(first==SIZE)
            first = 0;
        return queue[first];
    }

    int getSize(){ return size; }
};

class Action{
    int previousActions[MAXDEPTH], currentStep, x, y, nextMove;

    void move(int direction){
        if(direction == N || direction == S)
            y+= movement[direction];
        if(direction == E || direction == W)
            x+= movement[direction];

//        cout << "My new position: (x,y) " << x << ", " <<y<<endl;
//        getch();
    }

    public:
    Action(){
        x = y = currentStep = 0;
        cout << "This shouldnt happen!" << endl;
        getch();
    }

    Action(int x_, int y_, int currentStep_, int nextMove_){
        x = x_; y = y_;
        currentStep = currentStep_;
        nextMove = nextMove_;

        cout << "New action created! x: " << x << ", y: "<< y <<", CurrentStep: "<< currentStep<<", next move: "<<directions[nextMove]<<endl;
        //getch();
    }

    bool areWeThereYet(){
        if(x == 0 && y == 0) return true;
        return false;
    }

    void printMe(){
        cout << "X: " << x << ", Y:" << y << endl;
    }

    bool execute(MyQueue<Action*>* mQ){
        this->move(nextMove);

        if(this->areWeThereYet())
            return true;  // Done!


        if(x<100 && x>-100 && y<100 && y>-100){
//            for(int i=0; i<4; i++){  // Enqueue the next 4 movements from this point
//                Action* newAction = new Action(x, y, currentStep+1, i);
//                mQ->enQueue(newAction);}
            if(x%EAST==0 || x&WEST == 0){
                cout << "East ok!\n";
                Action* newAction = new Action(x, y, currentStep+1, E);
                mQ->enQueue(newAction);}

            if(x%WEST==0 || x%EAST==0 ){
                cout << "West ok!\n";
                Action* newAction = new Action(x, y, currentStep+1, W);
                mQ->enQueue(newAction);}

            if(y%NORTH==0 || y%SOUTH==0){
                cout << "North ok!\n";
                Action* newAction = new Action(x, y, currentStep+1, N);
                mQ->enQueue(newAction);}

            if(y%SOUTH==0 || y%NORTH==0 ){
                cout << "South ok!\n";
                Action* newAction = new Action(x, y, currentStep+1, S);
                mQ->enQueue(newAction);}

        }
    }

        void executeDontMove(MyQueue<Action*>* mQ){


        if(x<100 && x>-100 && y<100 && y>-100){
//            for(int i=0; i<4; i++){  // Enqueue the next 4 movements from this point
//                Action* newAction = new Action(x, y, currentStep+1, i);
//                mQ->enQueue(newAction);}
            if(x%EAST==0 || x&WEST == 0){
                cout << "East ok!\n";
                Action* newAction = new Action(x, y, currentStep+1, E);
                mQ->enQueue(newAction);}

            if(x%WEST==0 || x%EAST==0 ){
                cout << "West ok!\n";
                Action* newAction = new Action(x, y, currentStep+1, W);
                mQ->enQueue(newAction);}

            if(y%NORTH==0 || y%SOUTH==0){
                cout << "North ok!\n";
                Action* newAction = new Action(x, y, currentStep+1, N);
                mQ->enQueue(newAction);}

            if(y%SOUTH==0 || y%NORTH==0 ){
                cout << "South ok!\n";
                Action* newAction = new Action(x, y, currentStep+1, S);
                mQ->enQueue(newAction);}

        }

    }



};

int myPow(int integ, int e){
    if(e ==0) return 1;
    return(integ * myPow(integ, e-1));
}


int main(string args[]){
    int x, y, steps, count = 0;
    MyQueue<Action*> *mQ = new MyQueue<Action*>();
    cout << "Start x: "; cin >> x;
    cout << "Start y: "; cin >> y;

    Action* a = new Action(x, y, 0, 0);
    a->executeDontMove(mQ);
    //mQ->enQueue(a);

    steps = mQ->getSize();


    bool done = false;

    while(!done){
        steps = mQ->getSize();
        cout << "Size: " << steps << endl;
        getch();
        for(int i = 0; i<steps; i++){
            Action *b = mQ->deQueue();
            b->printMe();
            getch();
            done = b->execute(mQ);
            //delete(b);
//            if(done){
//                b->printMe();
//                cout << "Halt!";
//                getch();}
        }
    }



    //cout << endl << leastSteps << " steps is needed" << endl;
    return 0;
}
